"""中心扩展算法：
如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。
那么可以事先写一个函数，在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
（即s[l]==s[r]，然后在不越界的前提下左移l，右移r），这样，如果输入相同的 l 和 r，
就相当于寻找长度为奇数的回文串，如果输入相邻的 l 和 r，则相当于寻找长度为偶数的回文串：
"""

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def palindrome(s, l, r):
            # 防止索引越界
            while l >= 0 and r < len(s) and s[l] == s[r]:
                # 双指针，向两边展开，左往左，右往右
                l -= 1
                r += 1
            # 返回以 s[l] 和 s[r] 为中心的最长回文串
            return s[l + 1:r]  # 结束循环时l比回文串的内容多左移了一个 r多右移了一个

        res = ''
        for i in range(len(s)):
            # 寻找 以 i 为中心的回文子串
            sub1 = palindrome(s, i, i)
            # 寻找以 i，i+1为中心的回文子串
            sub2 = palindrome(s, i, i + 1)
            # 更新答案
            res = sub1 if len(sub1) > len(res) else res
            res = sub2 if len(sub2) > len(res) else res
        return res
